In wireless local area networks, network devices communicate with each other over a wireless medium that is shared among the network devices. In such cases, in which a wireless medium is shared among multiple network devices, in order to avoid interference among respective transmissions of the network devices on the wireless medium, generally only one networking device should be permitted to transmit on the wireless medium at any given time. When transmissions of multiple network devices interfere on a wireless medium, such occurrences are commonly referred to as “collisions”. According to IEEE Standard 802.11-2012, the entire disclosure of which is here incorporated by reference, a carrier sense multiple access with collision avoidance (CSMA/CA) scheme is therefore defined.
According to CSMA, prior to transmitting, a network device senses whether the wireless medium is busy—i.e., whether a carrier signal from another station's transmission is present on the wireless medium. If the wireless medium appears to be free based on carrier sensing, a collision avoidance scheme causes the networking device to select a randomized period of time to wait before transmitting. If the wireless medium remains free during this period of time, the network device begins transmitting upon conclusion of the period of time. The networking device expects to receive an acknowledgement from the destination of the transmission. If no acknowledgment is received, the network device may assume that a collision occurred, and therefore attempt to retry transmission later, possibly after waiting for an even longer randomized period of time.
In FIG. 1, an example illustration of a collision avoidance scheme 100 consistent with IEEE 802.11 is shown. At time 102, the medium ceases to be busy. A network device that desires to transmit on the medium will initially wait for the medium to remain free for a predetermined amount of time—a delay referred to as the distributed coordination function (DCF) interframe space (DIFS)—the ending of which is represented in FIG. 1 at time 106. At the end of the DIFS, the network device randomly selects an integer that can range from zero to an upper limit. The integer randomly selected may be referred to as a backoff number, a backoff delay, or a backoff interval. The network device then additionally waits for an amount of time corresponding to the selected backoff interval and, assuming the medium continues to remain free during this time, the network device can begin transmitting on the medium.
In FIG. 1, if the randomly selected backoff interval is zero, the network device can immediately begin transmitting on the medium at time 106. If the backoff interval selected is one, the network device waits for a predetermined time period referred to as a slot time, and can begin transmitting at time 110. Similarly, if the backoff interval selected is two, the network device can begin transmitting at time 114, which time corresponds to two slot times after the end of DIFS at time 106.
As shown in FIG. 1, a duration of a DIFS (referred to herein as a “DIFS duration” corresponds to two slot times and one short interframe space (SIFS). Because network devices will normally wait a DIFS duration prior to transmitting on a medium, even if the selected backoff is zero, an access point can gain precedence over regular network devices by beginning transmission on the medium during the DIFS duration, such as at time 118. The delay from time 102 until time 118 is called a point coordination function (PCF) interframe space (PIFS). As shown in FIG. 1, a duration of a PIFS corresponds to one SIFS and one slot time.
In FIG. 2, an example transmission following the backoff interval is shown. At time 150, a source transmits a request to send (RTS) to a destination. Following a SIFS, during which the destination processes the RTS and gets ready for transmission, the destination transmits a clear to send (CTS) frame at time 154. When the source receives a CTS frame, the source knows that the destination successfully received the RTS frame and that a collision did not occur. Because the RTS frame is relatively short, the determination of whether a collision has occurred will be much quicker than if a long data frame experienced a collision. In addition, the CTS frame signals to other network devices, which may not have received the RTS from the source, that a transmission is expected and that the medium is busy.
At time 158, after a further SIFS, the source begins transmission of data to the destination. At time 162, following another SIFS, the destination transmits an acknowledgment to the source if the destination correctly received the data. At time 166, the medium is once again free, and other network devices must wait for at least a period of DIFS until time 170 before the other network devices can begin transmission. Between time 150 and time 170, any network devices that had a non-zero backoff would have deferred decrementing their backoff until time 170. In other words, if another device had a remaining backoff of two at time 150, that backoff would begin decrementing once again at time 170. If the medium remains free, after an additional two slot times, the backoff will have decreased to zero and that network device can transmit.
In order to provide quality of service (QoS)—i.e., giving different priorities to different types of traffic—the collision avoidance scheme above, which is called the distributed coordination function (DCF), has been extended with a scheme called enhanced distributed channel access (EDCA). Under EDCA, two primary changes are made. The first is that a duration of the DIFS is effectively lengthened for lower priority traffic. In addition, the average backoff interval for lower priority traffic is lengthened. The following table includes the four access categories defined for 802.11 QoS. The lowest priority is called background, while the highest priority is called voice.
AccessACCWminCWmaxCategoryDescriptionCWmine.g.CWmaxe.g.AIFSNAC_BKBackgroundaCWmin15aCWmax10237AC_BEBest Effort aCWmin15aCWmax10233AC_VIVideo(aCWmin + 1)/2 − 17aCWmin152AC_VOVoice(aCWmin + 1)/4 − 13(aCWmin + 1)/2 − 172
When selecting a backoff interval, the network device selects a random number between 0 and an upper limit. The upper limit is called a contention window (CW) and is initialized to a value called CWmin. When a transmission fails, likely as a result of collision, the contention window is increased, up to a limit of CWmax. The above table demonstrates that the values of CWmin and CWmax are different for different access categories.
The values of CWmin and CWmax are defined in terms of parameters aCWmin and aCWmax. Using example values of 15 for aCWmin and 1023 for aCWmax, examples of CWmin and CWmax for each access category are shown. For example, for video (AC_VI), the contention window begins at 7 where the backoff will be randomly selected from the range of 0 to 7, and after one or more retries, the backoff will be randomly chosen from the range of 0 to 15.
The above table also has a column for arbitration interframe space number (AIFSN), which specifies the minimum time that the medium must be free before the backoff interval begins. The arbitration interframe space (AIFS) is specified by the sum of SIFS and AISFN times the slot time. As shown in FIG. 3, the duration of an AIFS for an AIFSN of two is the same as the duration of the DIFS from FIG. 1. The duration of an AIFS for an AIFSN of three is one slot time longer than the duration of the DIFS. Similarly, the duration of an AIFS for an AIFSN of 7 is five slot times longer than the duration of the DIFS. In other words, for best effort (AC_BE) frames, where the AIFSN is three, the earliest time a network device could transmit best effort data is at time 204. If the selected backoff is one, best effort traffic could be transmitted starting at time 208. Similarly, if the backoff is two, best effort traffic could begin transmitting at time 212, etc.
Using background data (AC_BK) as an example, the contention window, using the example aCWmin and aCWmax values, increases from 15 to a maximum of 1023 as retransmissions are attempted. Once the contention window reaches CWmax, the contention window remains the same for any subsequent retries. Eventually, after a certain number of retries, transmission of that frame may be abandoned. The function that specifies how the contention window increases from CWmin to CWmax may be dependent on access category. One example function, which is nearly equivalent to doubling, is (CW+1)*2−1. In other words, the contention window begins at 15 and, after an unsuccessful transmission, the CW increases to 31. After another failed transmission attempt, the contention window increases to 63, etc.
Referring again to FIG. 3, it can be observed that the total delay from the medium becoming free until a transmission begins can be expressed in terms of SIFS plus a number of slot times. SIFS is based on the nominal time that the medium access control (MAC) and physical layer interface (PHY) require in order to receive the last symbol of a frame at the air interface, process the frame, and respond with the first symbol on the air interface of the earliest possible response frame. IEEE 802.11-2012, section 6.5.4.2.
The slot time is based on four values: aMACProcessingDelay, aAirPropagationTime, aRxTxTurnaroundTime, and aCCATime. The aMACProcessingDelay value is the maximum time available for the MAC to request a transmission from the PHY after learning of the end of a reception by the PHY. The aAirPropagationTime is twice the propagation time required for a signal to cross the distance between the most distant allowable network devices. The aRxTxTurnaroundTime is the maximum time required by the PHY to change from receiving to transmitting. The aCCATime is the maximum time that a clear channel assessment (CCA) mechanism has available to determine whether the medium is busy or idle. See IEEE 802.11-2012, section 6.5.4.2. For purposes of illustration only, examples of these values in the 5 GHz band are 9 μs for slot time, 16 μs for SIFS, and 4 μs for aCCATime.